package 代码随想录.单调栈.柱状图中最大的矩形;

public class LeetCode84 {
    //方法一：暴力(超时)
    //从当前柱子开始逐步向两边扩散，找到第一个比当前柱子高度小的柱子所在下标
    public int largestRectangleArea(int[] heights) {
        int maxArea = 0;
        int len = heights.length;
        for (int i = 0; i < len; i++) {
            int left = i;
            int right = i;
            //找左边第一个高度小于当前柱子的下标
            while (left >= 0 && heights[left] >= heights[i]) {
                left--;
            }
            //找右边第一个高度小于当前柱子的下标
            while (right < len && heights[right] >= heights[i]) {
                right++;
            }
            //计算宽度
            int w = right - left - 1;
            //计算高度
            int h = heights[i];
            maxArea = Math.max(maxArea, w * h);
        }
        return maxArea;
    }

    public static void main(String[] args) {
        LeetCode84 code84 = new LeetCode84();
        int[] heights = {2, 1, 5, 6, 2, 3};
        System.out.println(code84.largestRectangleArea(heights));
    }
}
